"""
给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""
from typing import List


class Solution:

    def exist(self, board: List[List[str]], word: str) -> bool:
        # 4个方向
        d = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        # 访问过的地址

        if not board:
            return False

        m = len(board)
        n = len(board[0])

        def valid_area(x: int, y: int):
            # 是否是合法的坐标
            return x >= 0 and y >= 0 and x < m and y < n

        def search(x: int, y: int, index: int, visited):
            """ x轴坐标，y轴坐标, word第几个
            """
            # print("i=",x,"y=",y)
            if not word:
                return False

            if board[x][y] != word[index]:
                return False

            if (x,y) in visited:
                return False

            if len(word) == index + 1 :
                return word[index] == board[x][y]

            # visited[(x, y)] = True
            for i in d:
                new_x = x + i[0]
                new_y = y + i[1]
                if not valid_area(new_x, new_y):
                    continue
                
                if word[index]== board[x][y]:
                    print("new_x", new_x, "new_y",new_y, "index=",index, word[index:], board[new_x][new_y] == word, len(word))
                print("visited=", visited)
                if len(word) == index+1:
                    print('.............')
                    return True
                if search(new_x, new_y, index+1, {**visited, (x,y): True}):
                    return True

        for i in range(len(board)):
            for j in range(len(board[0])):
                if search(i, j, 0, {}):
                    return True
        else:
            return False


if __name__ == "__main__":
    b = [["A","B","C","E"],
        ["S","F","E","S"],
        ["A","D","E","E"]]
    w ="ABCEFSADEESE"
    res = Solution().exist(b, w)

    print(res)
